package leetcode; /**
 * description:
 * author:zt
 * date:2021-08-12
 */

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 */
public class leetcode22 {
    List<String> ans = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        if (n==0) return ans;
        dfs("",n,n);
        return ans;
    }
    public void dfs(String res,int left,int right){
        if (left==0 && right==0){
            ans.add(res);
            return;
        }
        if (left>right) return;
        if (left>0) dfs(res+"(",left-1,right);
        if (right>0) dfs(res+")",left,right-1);
    }
}
